#include <stdio.h>

int max_sub(int arr[], int length, int* start, int* end)
{
  int max, bmax;
  int i;
  int s,e,bs=0,be=-1;
  max = 0;
  bmax = 0;
  for(i=0; i<length; ++i){
    bmax = bmax + arr[i];
    if(bmax<=0){
      bs = i+1;
      be = i;
      bmax = 0;
    }
    else{
      ++be;
    }
    if(bmax>max){
      max = bmax;
      s = bs;
      e =be;
    }
    
  }
  *start = s;
  *end = e;
  return max;
}

int main()
{
  int arr[] = {31,-41,59,26,-53,58,97,-93,-23,84};
  int i,j, maxsum;
  for(i = 0; i<10; ++i)
    printf("%d\t",arr[i]);
  puts("");

  maxsum = max_sub(arr, 10, &i, &j);
  if(maxsum > 0){
    printf("The maximum subarray is from %d to %d\n",arr[i],arr[j]);
    printf("The maximum sub is %d\n", maxsum);
  }
  
  return 0;
}
